package com.hy;


/**
 * Created With IntelliJ IDEA.
 * Descriptions:1594. 矩阵的最大非负积
 * 给你一个大小为 m x n 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。
 * 在从左上角 (0, 0) 开始到右下角 (m - 1, n - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元
 * 格中所有整数的乘积。
 * 返回 最大非负积 对 109 + 7 取余 的结果。如果最大积为 负数 ，则返回 -1 。
 * 注意，取余是在得到最大积之后执行的。
 * User:Mr.Du
 * Date:2024/7/2
 * Time:17:58
 */
public class MaxProductPath {

    /**
     * 计算网格中从左上角到右下角路径的最大乘积。
     * 使用动态规划方法，dpMax[i][j]表示到达(i, j)点的最大乘积，dpMin[i][j]表示最小乘积。
     * 乘积的符号决定了使用最大值还是最小值来更新dpMax数组。
     *
     * @param grid 网格数组，每个元素代表路径上的系数。
     * @return 返回从左上角到右下角的路径上最大乘积，如果结果为负数则返回-1。
     */
    public int maxProductPath(int[][] grid) {
        // 网格的行数和列数
        int m = grid.length, n = grid[0].length;
        // 初始化动态规划数组，dpMax和dpMin分别代表最大乘积和最小乘积
        long[][] dpMax = new long[m][n];
        long[][] dpMin = new long[m][n];
        // 初始化起点的最大和最小乘积
        dpMax[0][0] = dpMin[0][0] = grid[0][0];
        // 初始化第一行的最大和最小乘积
        for (int i = 1; i < n; i++) {
            dpMax[0][i] = dpMin[0][i] = dpMax[0][i - 1] * grid[0][i];
        }
        // 初始化第一列的最大和最小乘积
        for (int i = 1; i < m; i++) {
            dpMax[i][0] = dpMin[i][0] = dpMax[i - 1][0] * grid[i][0];
        }
        // 动态规划填充剩余位置的最大和最小乘积
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                long m1 = dpMax[i - 1][j], n1 = dpMax[i][j - 1];
                long m2 = dpMin[i - 1][j], n2 = dpMin[i][j - 1];
                long t = grid[i][j];
                // 根据当前网格元素的值决定使用最大值还是最小值来更新dpMax数组
                if (t >= 0) {
                    dpMax[i][j] = Math.max(m1, n1) * t;
                    dpMin[i][j] = Math.min(m2, n2) * t;
                } else {
                    dpMax[i][j] = Math.min(m2, n2) * t;
                    dpMin[i][j] = Math.max(m1, n1) * t;
                }
            }
        }
        // 返回最终结果，如果结果为负数则返回-1
        return dpMax[m-1][n-1] < 0 ? -1 : (int) (dpMax[m-1][n-1] % 1000000007);
    }

    public static void main(String[] args) {
        int[][] grid = new int[][]{{-1,-2,-3},{-2,-3,-4},{-3,-4,-5}};
        MaxProductPath maxProductPath = new MaxProductPath();
        System.out.println(maxProductPath.maxProductPath(grid));
    }
}
